/**
 * 从前序与中序遍历序列构造二叉树
 *
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 * 示例 1:
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 *
 * 示例 2:
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 *
 * 提示:
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder 和 inorder 均 无重复 元素
 * inorder 均出现在 preorder
 * preorder 保证 为二叉树的前序遍历序列
 * inorder 保证 为二叉树的中序遍历序列
 */

/**
 * 首先前序遍历 和 中序遍历 是什么?
 * 前序遍历的第一个节点肯定是这颗树的根节点的
 * 然后我们在中序遍历里找这个节点, 我们会发现中序遍历被分成了
 * 两个部分, 这两个部分分别就可以组成这个根节点的左子树和右子树
 * 但是我们怎么从左子树中找到根节点呢? 其实这个不难, 其实我们的
 * 前序遍历的第二个就是根节点的左子树根节点, 那么右子树的根节点
 * 又要怎么去找呢? 我们发现前序遍历中只有左子树全都遍历完后面的
 * 节点就是我们右子树的根节点, 于是, 我们可以写出一个递归, 前面
 * 是不断的处理左子树, 等到左子树处理完毕, 就开始处理右子树
 * 因为要处理完左子树, 所以我们要在递归的函数头上加上区间来完成
 * 左子树的遍历
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 */

public class Main {

    // 使用一个数记录我们前序遍历使用到哪个数了
    public int target = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // 递归函数, 这里我们要处理的是中序遍历, 所以用中序遍历
        return buildTree(preorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder, int start, int end) {

        // 区间不符合要求, 返回 null
        if (start > end) {
            return null;
        }

        // 构造根节点
        TreeNode root = new TreeNode(preorder[target]);

        // 根节点在中序遍历中的位置
        int cur = findNum(inorder, preorder[target], start, end);

        // 每使用一次, 目标位置就要加 1
        target++;

        // 左子树是左边构成的
        root.left = buildTree(preorder, inorder, start, cur - 1);

        // 右子树是右边构成的
        root.right = buildTree(preorder, inorder, cur + 1, end);

        // 返回根节点
        return root;
    }

    // 在中序遍历中寻找目标数的位置
    // 可以使用 hash 优化时间复杂度
    public int findNum(int[] inorder, int num, int start, int end) {

        for (int i = start; i <= end; i++) {
            if (inorder[i] == num) {
                return i;
            }
        }

        // 找不到就返回 -1, 肯定是能找到的, 这里是为了照顾编译器
        return -1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}